package com.kenliang.algorithm.sort;

import java.util.Random;

/**
 * @author KenLiang
 * @description:快速排序，随机快排 时间复杂度O(N*logN) 空间复杂度O(1)
 * @date Created in 14:55 2021/1/2.
 */
public class QuickSort implements ISort {

    @Override
    public int[] sort(int[] in) {
        if(in==null || in.length<2){
            return in;
        }
        int[] result = this.process(0, in.length - 1, in);
        if (result!=null){
            this.quickSort(result,in);
        }
        return in;
    }

    private void quickSort(int[] result,int[] in){
        if (result!=null){
            this.quickSort(this.process(result[0],result[1],in),in);
            this.quickSort(this.process(result[2],result[3],in),in);
        }
    }


    /**
     * 荷兰国旗问题
     * 将数组in从start到end位置的值比基准数字小的放左边，等于的在中间，大于的在右边，大于区小于区顺序不保证
     *
     * @param start 数组开始index
     * @param end   数组结束index
     * @param in    数组
     * @return 数组第一二个值为处理后的小于区的左右边界index, 第三四个值为大于区的左右边界index
     * @author KenLiang
     * @date 2021/1/21 4:12 PM
     */
    private int[] process(int start, int end, int[] in) {
        if ( start >= end  ) {
            return null;
        }
        //取最后一个数字作为基准数字，普通快速排序，如果是1，2，3，4，5，6时间复杂度为O(N**2)
        //增加此行变为随机快排，随机选择一个数字作为基准数字，概率统计算下来的时间复杂度为O(N*logN)
        this.swap(in,start + (int)(Math.random()*(end-start+1)),end);
        int standardNum = in[end];
        int smallBoundary = start - 1;
        int bigBoundary = end ;
//        System.out.println("-----------------------------");
//        this.soutArray(in);
//        System.out.println("---start---");
        for (int i = start; i < bigBoundary; ) {
            if(in[i]<standardNum){
                //小于基准数字，小于区左边界加1，index加1
                smallBoundary++;
                this.swap(in,i,smallBoundary);
                i++;
            }else if(in[i]>standardNum){
                //大于基准数字，大于区右边界减1，index不加，因为新换过来的数字没有进行过比较
                bigBoundary--;
                this.swap(in,i,bigBoundary);
            }else{
                //等于基准数字，index加1
                i++;
            }
//            System.out.print("i="+i+":  ");
//            this.soutArray(in);
        }
        this.swap(in,bigBoundary,end);
        bigBoundary++;
        int[] result = {start, smallBoundary, bigBoundary, end};
//        System.out.println("---end---");

//        this.soutArray(in);
//        this.soutArray(result);
//        System.out.println("-----------------------------");
        return result;

    }

    public static void main(String[] args) {
        System.out.println(Math.random());
    }


}
